Cuộc bầu cử đa sắc tộc đầu tiên ở Nam Phi với quyền bỏ phiếu được trao cho tất cả mọi người đã diễn ra vào ngày 27 tháng 4 năm 1994. ANC giành được 62% số phiếu bầu, và Mandela, với vai trò là lãnh đạo ANC, đã nhậm chức làm Tổng thống da đen đầu tiên của Nam Phi vào ngày 10 tháng 5 năm 1994, de Klerk của Đảng Quốc gia là phó tổng thống thứ nhất và Thabo Mbeki là phó tổng thống thứ hai trong Chính phủ Thống nhất Quốc gia.[74] Với vị trí là Tổng thống từ tháng 5 năm 1994 cho đến tháng 6 năm 1999, Mandela đã chủ trì sự chuyển giao từ quyền lực của thiểu số và chủ nghĩa apartheid, giành được sự tôn trọng của quốc tế đối với những nỗ lực hòa giải quốc gia và thế giới của ông.[75] Mandela đã khích lệ những người Nam Phi da đen ủng hộ cho đội Springbok (đội tuyển rugby quốc gia Nam Phi) trước đây bị dân chúng ghét bỏ khi Nam Phi tổ chức Cúp Rugby Thế giới 1995.[76] Sau khi Springbok giành chiến thắng trong trận chung kết trước New Zealand, Mandela đã trao cúp vô địch cho đội trưởng Francois Pienaar, một người Afrikan, trên người mặc chiếc áo đấu Springbok với con số 6 của Pienaar sau lưng. Hành động này được xem là bước tiến lớn của sự hòa giải giữa người Nam Phi da trắng và da đen.[77]

Sau khi nhậm chức tổng thống, một trong những dấu hiệu đặc trưng của Mandela là chiếc áo Batik của ông, còn được biết đến với cái tên "Áo Madiba", kể cả trong những sự kiện long trọng.[78] Trong hành động quân sự đầu tiên sau thời kỳ apartheid của Nam Phi, Mandela đã ra lệnh cho quân đội xâm nhập lãnh thổ Lesotho vào tháng 9 năm 1998 để bảo vệ chính quyền của Thủ tướng Pakalitha Mosisili. Vụ việc này diễn ra sau một cuộc bỏ phiếu gây tranh cãi trong đó lực lượng phản đối đã đe dọa đến chính quyền thiếu ổn định này.[79] Những nhà bình luận và phê bình trong đó có cả các nhà hoạt động vì AIDS như Edwin Cameron đã chỉ trích Mandela vì sự thiếu hiệu quả của chính quyền ông trong việc ngăn chặn cuộc khủng hoảng AIDS.[80][81] Sau khi nghỉ hưu, Mandela thừa nhận rằng ông đã thất bại vì đã không chú ý nhiều hơn đến bệnh dịch HIV/AIDS.[82][83] Mandela từ đó đã có một số bài phát biểu chống lại bệnh dịch AIDS.[84][85]

Vụ xử Lockerbie

Tổng thống Mandela có sự quan tâm đặc biệt trong việc giúp đỡ giải quyết tranh cãi kéo dài giữa một bên là quốc gia Lybia dưới thời Gaddafi, còn bên kia là Hoa Kỳ và Anh, đối với việc mang ra xét xử hai người Lybia bị truy tố vào tháng 11 năm 1991 và bị buộc tội phá hoại Chuyến bay 103 của Pan Am, khiến nó rơi tại thị trấn Lockerbie của Scotland ngày 21 tháng 12 năm 1988, làm cho 270 người thiệt mạng.[86] Từ đầu năm 1992, Mandela đã có lời đề nghị không chính thức gửi tới Tổng thống George H.W. Bush yêu cầu xét xử hai nghi phạm Lybia tại quốc gia thứ ba. Bush tỏ ra tán thành đề nghị này, cả Tổng thống François Mitterrand của Pháp và Vua Juan Carlos I của Tây Ban Nha cũng vậy.[87] Vào tháng 11 năm 1994 – sáu tháng sau khi ông đắc cử tổng thống – Mandela chính thức đề nghị Nam Phi nên là nơi diễn ra phiên toàn xét xử vụ đánh bom Chuyến bay 103 của Pan Am.[88]

Tuy nhiên, Thủ tướng Anh John Major thẳng thừng từ chối ý tưởng này nói rằng chính phủ Anh không tin tưởng vào tòa án nước ngoài.[89] Đến ba năm sau, Mandela một lần nữa lại gửi lời đề nghị đến người kế nhiệm Major, Tony Blair, khi ông có chuyến viếng thăm Luân Đôn vào tháng 7 năm 1997. Cuối năm đó, tại Cuộc họp những người đứng đầu chính phủ của khối Thịnh vượng chung năm 1997 tại Edinburgh tháng 10 năm 1997, Mandela đã cảnh báo:

"Không thể có một quốc gia vừa là nguyên cáo, vừa là bên nguyên lẫn quan tòa."

Cuối cùng đã có một thỏa hiệp để tổ chức phiên tòa ở Trại quân sự Zeist ở Hà Lan, xét xử theo Luật Scotland, và Tổng thống Mandela bắt đầu thương thuyết với Đại tá Gaddafi để dẫn độ hai bị cáo (Megrahi và Fhimah) vào tháng 4 năm 1999.[90] Sau phiên tòa kéo dài 9 tháng, phán quyết đã được công bố vào ngày 31 tháng 1 năm 2001. Fhimah được tuyên trắng án, nhưng Megrahi bị buộc tội và phải lãnh 27 năm tù trong một nhà tù ở Scotland. Kháng cáo lần đầu của Megrahi đã bị bác vào tháng 3 năm 2002, và cựu tổng thống Mandela đã đến thăm người này tại nhà tù Barlinnie vào ngày 10 tháng 6 năm 2002.

'Megrahi hoàn toàn cô độc', Mandela nói trong cuộc họp báo nhỏ trong phòng thăm viếng của nhà tù. 'Anh ta không có ai để nói chuyện cả. Đây là sự hành hạ về tâm lý mà một người đàn ông phải chịu đựng trong suốt thời gian dài chịu án hoàn toàn một mình. Sẽ công bằng hơn nếu anh ta được chuyển đến một quốc gia Hồi giáo — và có nhiều quốc gia Hồi giáo mà phương Tây tin tưởng. Nó sẽ giúp gia đình anh dễ viếng thăm anh hơn nếu anh ở một nơi như vương quốc Maroc, Tunisia hay Ai Cập.'[91]

Megrahi sau đó được chuyển đến nhà tù Greenock và không còn bị biệt giam nữa.[92] Tháng 8 năm 2009, Megrahi, sau khi được chẩn đoán bị ung thư và chỉ còn sống được 3 tháng, đã được trả tự do trong một đợt ân xá và được phép trở về Libya. Quỹ Nelson Mandela đã ủng hộ quyết định ân xá cho Megrahi trong một bức thư gửi tới Chính quyền Scotland thay mặt cho Mandela.[93]